package gold.digger;

import gold.utils.InputUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC684 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 有意思的并查集解法
     * @return:
     */
    class Solution {
        //缓存结果集
        int[] result = new int[2];

        public int[] findRedundantConnection(int[][] edges) {
            int[] father = new int[edges.length + 1];
            for (int i = 0; i < father.length; i++) {
                father[i] = i;
            }
            for (int[] edge : edges) {
                union(father, edge[0], edge[1]);
            }
            return result;
        }

        //路径压缩
        public int findXFather(int[] father, int x) {
            while (father[x] != x) {
                father[x] = father[father[x]];
                x = father[x];
            }
            return x;
        }

        //合并两个能连接上的点，father合为最后确定的father
        public void union(int[] father, int x, int y) {
            int xFather = findXFather(father, x);
            int yFather = findXFather(father, y);
            if (xFather != yFather) {
                father[xFather] = yFather;
            } else {
                //在发现两个点的连接已经存在时，就更新缓存，题目要最后一个，遍历到最后一个就是结果
                result[0] = x;
                result[1] = y;
            }
        }

    }


    class Solution_Fail_not_because_hard_but_for_their_weird_request {
        public int N = 2;//总节点个数

        public int[] findRedundantConnection(int[][] edges) {
            //先获取N，节省空间
            for (int[] edge : edges) {
                int start = edge[0], end = edge[1];
                N = Math.max(N, end);//因为描述里，end已经确保比start大
            }

            List<Integer>[] graph = new List[N + 1];
            for (int[] edge : edges) {
                int start = edge[0], end = edge[1];
                if (graph[start] == null) graph[start] = new ArrayList<>();
                graph[start].add(end);
                if (graph[end] == null) graph[end] = new ArrayList<>();
                graph[end].add(start);
            }

            int maxConnect = 0, maxIdx = 0;
            boolean changed = false;
            for (int i = 1; i <= N; i++) {
                List<Integer> node = graph[i];
                if (node.size() > maxConnect) {
                    if (i < N && graph[i].size() != graph[i + 1].size()) changed = true;
                    if (i == N && graph[i].size() != graph[i - 1].size()) changed = true;
                    maxConnect = node.size();
                    maxIdx = i;
                }
            }

            if (!changed) return edges[edges.length - 1];
            boolean[] visited = new boolean[N + 1];
            List<Integer> loopNextList = new ArrayList<>();
            for (int i = 0; i < graph[maxIdx].size(); i++) {
                int next = graph[maxIdx].get(i);
                visited[next] = true;
                if (dfs(graph, visited, next, maxIdx)) loopNextList.add(next);
                visited[next] = false;
            }

            int[] res = new int[2];
            res[0] = maxIdx;
            res[1] = loopNextList.get(loopNextList.size() - 1);
            return res;
        }

        public boolean dfs(List<Integer>[] graph, boolean[] visited, int cur, int pre) {
            for (int i = 1; i < N + 1; i++) {
                if (pre == i || cur == i || !graph[cur].contains(i)) continue;
                if (pre != i && cur != i && visited[i]) return true; //已经遍历过，认为出现环
                visited[i] = true;
                if (dfs(graph, visited, i, cur)) return true;
                visited[i] = false;
            }
            return false;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[][] edges = InputUtil.toDoubleIntegerArray("[[1,2],[2,3],[3,4],[1,4],[1,5]]");
        System.out.println(Arrays.toString(solution.findRedundantConnection(edges)));
    }

    public static void main(String[] args) throws Exception {
        LC684 an = new LC684();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
